In structured programming, transitions of program execution to a called program, and returns to the execution of the calling program--such as occur on subroutine calls and returns--require the storing and restoration of information linking the called program to the calling program. For purposes of this discussion, both the calling programs and the called programs will commonly be referred to as subprograms. Linking or linkage information of a subprogram herein refers to information associated with the subprogram, such as arguments or parameters, local variables, general register contents, program counter contents, the process status word, the return values calculated by a subprogram, and the like.
Modern structured programming relies heavily on the use of subprograms, and therefore the moving of linking information in and out of storage can become a major overhead in such a programming environment. Thus, to be able to implement structured programming and still obtain high system efficiency, program level linkage must be optimally implemented.
This objective is approached by utilizing a stack dedicated to storing linkage information, and implementing the stack at least in part in a cache memory. However, the stack frames, each one of which contains the items of information linking a single called program to its calling program, have not been made all of the same size, and to keep track of where each frame begins, it has been necessary to calculate and store a pointer for each frame, which pointer indicates the starting address of that frame. This bookkeeping function undesirably adds to program overhead.
Furthermore, to access an item of information within such a stack frame, the item's frame pointer offset must be added to the frame pointer to arrive at its address. The overhead of pointer offset addition incurred each time an item must be accessed can place a noticeable limitation on system performance.
An acute example of this limitation is the treatment of general registers within such systems. Many conventional systems have only one set of general registers, and at every transition of program execution from a calling to a called program the contents of the general registers must be stored to free them for use during execution of the called program; on return of program execution to the calling program, the contents of the general registers must be restored. This characteristic makes the contents of the general registers suited for inclusion in the linkage information stored in a stack. Due to the overhead associated with indirect, offset addition, addressing of stack information, however, system performance is markedly limited by the storage and retrieval of general register contents.
An alternative prior art scheme directly implements general registers in a separate cache memory, which is organized as a stack but which is dedicated to general registers. A separate set of general registers is associated with each subprogram. This scheme avoids the overhead of general register saves and restores. But it requires a controller to interleave its activities, working alternatively with the linkage information stack and the general register stack, and to work with two sets of pointers, one for the linkage information stack and another for the general register stack. This adds much complexity to the system and again places a significant limitation on system performance.